//
//  Tree.h
//  TreeProject
//
//  Created by John Phillips on 3/2/12.
//
// Tree class. This class is designed to be very general purpose
// but also extremely extensible and useable for anybody. 
//
#include <iostream>
#include <iterator>

#include <cassert>
#ifndef SGCTree_h
#define SGCTree_h

namespace SGCTypes {

  using namespace std;
  //basic node class that will be the nodes of the tree. Minimal error checking,
  //consists of mostly simple getters and accessors. 
  template <typename T>
    class Node {
  public:
    //typedefs
    typedef Node<T> NodeType;
    typedef Node<T> *NodePtrType;
    typedef T DataType;
    typedef T &DataRefType;
  private:
    //private members, the essential 'links' to others, and the data.
    DataType data;
    NodePtrType parent;
    NodePtrType rightSibling;
    NodePtrType leftSibling;
    NodePtrType leftmostChild;
    NodePtrType rightmostChild;
  public:
    //-----constructors
  Node():parent(NULL), 
      rightSibling(NULL), 
      leftSibling(NULL), 
      leftmostChild(NULL), 
      rightmostChild(NULL) {}
  Node(DataType newData): parent(NULL), 
      rightSibling(NULL), 
      leftSibling(NULL), 
      leftmostChild(NULL), 
      rightmostChild(NULL), 
      data(newData) {}
    //-----getters - these use assertions to prevent program flow from going too far.
    NodePtrType getParent(void) {
      assert(parent != NULL);
      return parent;
    }
    
    NodePtrType getRightSibling(void) {
      assert(rightSibling != NULL);
      return rightSibling;
    }
    
    NodePtrType getLeftSibling(void) {
      assert(leftSibling != NULL);
      return leftSibling;
    }
    
    NodePtrType getRightmostChild(void) {
      assert(rightmostChild != NULL);
      return rightmostChild;
    }
    
    NodePtrType getLeftmostChild(void) {
      assert(leftmostChild != NULL);
      return leftmostChild;
    }
    DataType getData(void) {
      return data;
    }

    
    //----setters
    //the setters use casserts. I'm not sure if this is a really good idea
    // or a really bad one.
    void setParent(NodePtrType newParent) {
      assert(newParent != NULL);
      parent = newParent;
    }
    void setLeftSibling(NodePtrType newLeftSibling) {
      assert(newLeftSibling != NULL);
      leftSibling = newLeftSibling;
      newLeftSibling->rightSibling = this;
    }
    void setRightSibling(NodePtrType newRightSibling) {
      assert(newRightSibling != NULL);
      rightSibling = newRightSibling;
      newRightSibling->leftSibling= this;
    }
    void setRightmostChild(NodePtrType newRightmostChild) {
      assert(newRightmostChild != NULL);
      rightmostChild = newRightmostChild;
    }
    void setLeftmostChild(NodePtrType newLeftmostChild) {
      assert(newLeftmostChild != NULL);
      leftmostChild = newLeftmostChild;
    }
    void setData(DataType newData) {
      data = newData;
    }
    //-----booleans - used for checking in the tree class.
    bool leftmostChildSet(void) {
      return leftmostChild != NULL;
    }
    
    bool rightmostChildSet(void) {
      return rightmostChild != NULL;
    }
    bool rightSiblingSet(void) {
      return rightSibling != NULL;
    }
    bool leftSiblingSet(void) {
      return leftSibling != NULL;
    }
    bool parentSet(void) {
      return parent != NULL;
    }
    //----------end class--------//
  };

  //forward declaration of the iterator class so Tree can use it.
  template <typename T>
    class TreeIterator;

  template<typename T>
    class Tree {
  public:
    typedef Node<T> NodeType;
    typedef Node<T> *NodePtrType;
    typedef Tree<T> TreeType;
    typedef Tree<T> *TreePtrType;
    //    typedef Tree<T> &TreeRefType;
    typedef T DataType;
    typedef TreeIterator<DataType> IteratorType;
  private:
    //rootNode - self exmplanatory.
    //endNode - used to signify the end, and *possibly* make this class 
    //even _more_ extensible by allowing linked trees, i.e. we link another 
    //root node to rootNode via endNode.
    NodePtrType rootNode;
    NodePtrType endNode; 
    bool endNodeAllocated;
  public:
    //-----constructors - pretty simple. There's the tricky issue of endNode
    // which is used to signify the end of the tree whilst iterating over it.
  Tree():rootNode(NULL), endNode(NULL) {
      endNode = new NodeType;
      endNodeAllocated=true;
    }
  Tree(NodePtrType newRoot): rootNode(newRoot) {
      assert(newRoot != NULL);
      endNode = new NodeType;
      endNodeAllocated = true;
      rootNode->setRightSibling(endNode);
    }
    //-----getters
    NodePtrType getRootNode(void) {
      assert(rootNode!= NULL);
      return rootNode;
    }
    NodePtrType getEndNode(void) {
      assert(endNode != NULL);
      return endNode;
    }
    IteratorType end(void) {
      assert(endNode != NULL);
      return IteratorType(this, endNode);
    }
    IteratorType begin(void) {
      assert(rootNode != NULL);
      return IteratorType(this, rootNode);
    }
    //-----setters
    void setRootNode(NodePtrType newRoot) {
      assert(newRoot != NULL);
      rootNode = newRoot;
      rootNode->setRightSibling(endNode);
    }
    void setEndNode(NodePtrType newEnd) {
      assert(endNode != NULL); 
      endNodeAllocated=false;
      delete endNode;
      endNode = newEnd;
      if(rootNode)
	rootNode->setRightSibling(endNode);
    }
    void appendChild(NodePtrType newParent, NodePtrType child);
    void prependChild(NodePtrType newParent, NodePtrType child);

    //-----destructor
    ~Tree() { 
      if(endNodeAllocated)
	delete endNode;
    }
  };
  template<typename T>
    void Tree<T>::appendChild(NodePtrType newParent, NodePtrType child) {
    assert(newParent != NULL && child != NULL);
    if(!newParent->leftmostChildSet()) {
      newParent->setLeftmostChild(child);
    } 
    if(newParent->rightmostChildSet()) {
      NodePtrType curRightmostChild = newParent->getRightmostChild();
      curRightmostChild->setRightSibling(child);
      child->setLeftSibling(curRightmostChild);
    }
    newParent->setRightmostChild(child);
    child->setParent(newParent);
  }
  template <typename T>
    void Tree<T>::prependChild(NodePtrType newParent, NodePtrType child) {
    assert(newParent != NULL && child != NULL);
    if(!newParent->rightmostChildSet()) {
      newParent->setRightmostChild(child);
    }
    if(newParent->leftmostChildSet()) {
      NodePtrType curLeftmostChild = newParent->getLeftmostChild();
      curLeftmostChild->setLeftSibling(child);
      child->setRightSibling(curLeftmostChild);
    }
    newParent->setLeftmostChild(child);
    child->setParent(newParent);
  }

  template<typename T>
class TreeIterator{
  public:
    typedef Node<T> NodeType;
    typedef Node<T> *NodePtrType;
    typedef Node<T> &NodeRefType;
    typedef Tree<T> TreeType;
    typedef Tree<T> *TreePtrType;
    typedef Tree<T> &TreeRefType;
    typedef TreeIterator<T> IteratorType;
    typedef TreeIterator<T> &IteratorRefType;
    typedef T DataType;
    typedef T &DataRefType;
    typedef T *DataPtrType;
  private:
    TreePtrType tree;
    NodePtrType node;
  public:
    //-----constructor
  TreeIterator():tree(NULL), node(NULL) {}
  TreeIterator(TreePtrType tree, NodePtrType node): tree(tree), node(node) {
      assert(tree != NULL);
      assert(node != NULL);
    }
    //-----operators
    NodeRefType operator*() const{
      return *node;
    }
    NodePtrType operator->() const {
      return &(operator*());
    }
    IteratorRefType operator++() {
      if(node->leftmostChildSet()) {
	node = node->getLeftmostChild();
      } else if(node->rightSiblingSet()) {
	node = node->getRightSibling();
      } else {
	NodePtrType parentNode = node->getParent();
	if(parentNode->rightSiblingSet()) {
	  node = parentNode->getRightSibling();
	} else {
	  node = tree->getEndNode();
	}
      }
      return *this;
    }
    IteratorType operator++(int) {
      IteratorType tmp = *this;
      ++*this;
      return tmp;
    }
    IteratorRefType operator--() {
      NodePtrType parentNodeLeftSib;
      if(node->rightmostChildSet()) {
	node = node->getRightmostChild();
      } else if(node->leftSiblingSet()) {
	node = node->getLeftSibling();
      } else if(node->parentSet() && 
		( (parentNodeLeftSib = node->getParent()->getLeftSibling()) != NULL) ){
	node = parentNodeLeftSib;
      } else {
	node = tree->getEndNode();
      }
	
					
      return *this;
    }
    IteratorType operator--(int) {
      IteratorType tmp = *this;
      --*this;
      return tmp;
    }
    bool operator==(const IteratorType &in) {
      return (in.node == node && in.tree == tree);
    }
    bool operator!=(const IteratorType &in) {
      return !operator==(in);
    }
  };
};
#endif
